﻿#include "PrimKruskal.h"

#define INFINITY INT_MAX

/* Prototypes */
static void runPrims(void);
static void runKruskals(void);
static void kruskals(matrixADT graph);
static bool createsCycle(matrixADT graph, nodeT node);
static bool isCycle(matrixADT graph, nodeT node, int *visited);
static void prims(matrixADT graph);

static void initializeMatrix(matrixADT matrix);
static void printMatrix(matrixADT matrix);

void runMst() {
	int choice, i;

	system("cls");
	printf("-- Tree (MST) --\n\n");
	printf(" %d. Prim's algorithm\n %d. Kruskal's algorithm\n 3. Back\n", PRIMS, KRUSKALS);
	printf("\n => ");
	choice = GetInteger();

	while (choice != 3) {
		switch (choice) {
			case PRIMS:	
				runPrims();
				system("pause");
				return;
			case KRUSKALS:
				runKruskals();
				system("pause");
				return;
			default:
				printf("Wrong choice.\n");
				choice = GetInteger();
				break;
		}
	}
}

static void runPrims() {
	matrixADT graph;

	system("cls");
	printf("-- Prims's Algorithm --\n");
	printf("Recommended graphs: graphX.txt (X = 1-5)\n");
	printf("\n => ");
	graph = loadGraph(Concat("graphs/", GetLine()));
	if (graph != NULL)
		prims(graph);
}

static void runKruskals() {
	matrixADT graph;

	system("cls");
	printf("-- Kruskals's Algorithm --\n");
	printf("Recommended graphs: graphX.txt (X = 1-4)\n");
	printf("\n => ");
	graph = loadGraph(Concat("./graphs/", GetLine()));
	if (graph != NULL)
		kruskals(graph);
}

static void kruskals(matrixADT graph){
	pqueueADT pqueue;
	matrixADT mst;
	int i, totalCost=0, row=0, col=0, size;
	nodeT node, node1, node2;
	
	// Initialize a new priority queue and a new matrix for the nodes.
	pqueue = NewPQueue(graph->size);

	// MST:
	mst = NewGraph(graph->size, graph->size);
	initializeMatrix(mst);

	// Queue all elements:
	size = graph->size;
	for (row=0; row<graph->size; row++) {
		for (col=0; col<graph->size; col++) {
			node.cost = graph->nodes[row][col];
			node.from = col;
			node.to = row;
			// Queue the node if an edge exist:
			if (graph->nodes[row][col] != 0)
				Enqueue(pqueue, node);
		}
	}

	// Dequeue everything:
	while (!IsEmpty(pqueue)) {
		node = DequeueMin(pqueue);
		if (node.from != node.to) {			
			// If edge creates a cycle - don't use it:
			if (!createsCycle(mst, node)) {
					mst->nodes[node.from][node.to] = 1;
					mst->nodes[node.to][node.from] = 1;
					printf("\nEdge: %c -> %c = %d", node.from+'A', node.to+'A', node.cost);
					totalCost += node.cost;
			}
		}
	}
	printf("\n\nTotal path cost: %d\n\n", totalCost);
}

static bool createsCycle(matrixADT graph, nodeT node) {
	int i, *visited;
	
	visited = NewArray(graph->size, int);
	for (i=0; i<graph->size; i++)
		visited[i] = 0;

	if (isCycle(graph, node, visited)) {
		free(visited);
		return TRUE;
	} else {
		free(visited);
		return FALSE;
	}
}

static bool isCycle(matrixADT graph, nodeT node, int *visited) {
	nodeT temp;
	int i;
	
	visited[node.from] = 1;

	if (graph->nodes[node.from][node.to] == 1)
		return TRUE;
	
	for (i=0; i<graph->size; i++)
		if (graph->nodes[node.from][i] == 1 && visited[i] != 1) {
			temp.from = i;
			temp.to = node.to;
			if (isCycle(graph, temp, visited))
				return TRUE;
		}
	return FALSE;
}


static void prims(matrixADT graph) {
	pqueueADT pqueue;
	matrixADT visitedNodes;
	int i, min, totalCost=0, row=0, col=0, size, counter=0;
	nodeT node;

	// Initialize a new priority queue and a new matrix for the nodes.
	pqueue = NewPQueue(graph->size);

	// Visited matrix:
	visitedNodes = NewGraph(graph->size, graph->size);
	initializeMatrix(visitedNodes);

	// Go through the graph:
	size = graph->size;
	while (counter<graph->size-1) {
		for (col=0; col<graph->size; col++) {
			if (graph->nodes[row][col] == 0) {
				graph->nodes[row][col] = INFINITY;
			}
			// Edge between row-col not already visited:
			if (visitedNodes->nodes[row][col] != 1 && visitedNodes->nodes[col][row] != 1) {
				node.to = col;
				node.from = row;
				node.cost = graph->nodes[row][col];
				Enqueue(pqueue, node);
				visitedNodes->nodes[row][col] = 1;
			}
		}
		node = DequeueMin(pqueue);
		row = node.to;
		counter++;
		totalCost += node.cost;
		printf("\nPath: %c -> %c = %d", node.from+'A', node.to+'A', node.cost);
	}
	printf("\n\nTotal path cost: %d\n\n", totalCost);
}

static void initializeMatrix(matrixADT matrix) {
	int col, row;
	
	for (row=0; row<matrix->size; row++)
		for (col=0; col<matrix->size; col++)
			matrix->nodes[row][col] = 0;
}

static void printMatrix(matrixADT matrix) {
	int col, row;
	
	for (row=0; row<matrix->size; row++) {
		for (col=0; col<matrix->size; col++)
			printf("%4d", matrix->nodes[row][col]);
		printf("\n");
	}
}
